package com.tgy.leetcode;

import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 12/27/20 1:34 PM
 *
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 *
 */
public class _84_柱状图中最大的矩形 {

    public int largestRectangleArea(int[] heights) {

        if (heights == null || heights.length == 0) {

            return 0;
        }

        int max = 0;
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        while (index < heights.length) {

            if (stack.isEmpty()) {

                stack.push(index++);
                continue;
            }

            Integer tmpIndex = stack.peek();

            if (heights[tmpIndex] <= heights[index]) {

                stack.push(index++);
            }else {

                tmpIndex = stack.pop();
                int startIndex = 0;
                while (!stack.isEmpty() && heights[tmpIndex] == heights[(startIndex =stack.peek())]) {

                    stack.pop();
                }

                if (stack.isEmpty()) {

                    startIndex = -1;
                }

                max = Math.max(max,(index - startIndex - 1) * heights[tmpIndex]);
            }
        }


        // 递增的最后索引
        int end = stack.peek();
        int cur;
        while (!stack.isEmpty()) {

            cur = stack.pop();

            if (stack.isEmpty()) {

                index = cur;
                break;
            }

            while (!stack.isEmpty() && heights[index = (stack.peek())] == heights[cur]) {

                stack.pop();
            }

            max = Math.max(max,(end - index) * heights[cur]);
        }


        max = Math.max(max,heights.length * heights[index]);

        return max;
    }
}
